package com.demo.java.OD551_600.OD588;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【连续出牌数量(B卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146570860
 */
public class OdMain {
    public static void main(String[] args) {
        // 创建扫描器对象来接收用户输入
        Scanner in = new Scanner(System.in);

        // 读取第一行输入的字符串并以空格分隔
        String[] str1 = in.nextLine().split(" ");
        // 读取第二行输入的字符串并以空格分隔
        String[] str2 = in.nextLine().split(" ");

        int n = str1.length;  // 获取字符串数组的长度，即牌的数量
        int[] used = new int[n];  // 用于标记哪些牌已经被使用过
        int ans = 0;  // 最终结果（最大连续出牌数量）

        // 遍历所有牌，尝试从每一张牌开始深度优先搜索
        for (int i = 0; i < n; i++) {
            // 通过 DFS 从当前牌开始搜索，计算能出多少连续的牌
            ans = Math.max(ans, dfs(str1, str2, i, used, 1));
        }

        // 输出最大连续出牌数量
        System.out.println(ans);
    }

    /**
     * 深度优先搜索 (DFS) 用来查找最大符合条件的排列
     * @param str1 第一个字符串数组，代表第一组牌的颜色
     * @param str2 第二个字符串数组，代表第二组牌的颜色
     * @param i 当前牌的位置
     * @param used 标记牌是否已被使用
     * @param ans 当前搜索的连续出牌数量
     * @return 最大连续出牌数量
     */
    public static int dfs(String[] str1, String[] str2, int i, int[] used, int ans) {
        // 如果当前牌已经使用过，或者超出范围，返回当前连续出牌数量减 1
        if (used[i] == 1 || i >= str1.length) {
            return ans - 1;
        }

        int res = ans;  // 当前最大连续出牌数量

        // 标记当前牌为已使用
        used[i] = 1;

        // 遍历其他所有牌，尝试匹配符合条件的牌
        for (int j = 0; j < str1.length; j++) {
            // 如果当前牌与其他牌不相同，且其他牌未被使用
            if (i != j && used[j] == 0) {
                // 如果两张牌的颜色相同（即str1或str2中的元素相等），可以连续出牌
                if (str1[i].equals(str1[j]) || str2[i].equals(str2[j])) {
                    // 递归搜索下一个符合条件的牌，出牌数量加 1
                    int t = dfs(str1, str2, j, used, ans + 1);
                    // 获取最大连续出牌数量
                    res = Math.max(res, t);
                }
            }
        }

        // 回溯，标记当前牌为未使用
        used[i] = 0;
        return res;  // 返回当前的最大连续出牌数量
    }
}
